import java.util.Arrays;

public class Main {
    public static void quickSort(int[] array){  //快速排序
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if (start >= end){
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partition(int[] array,int left,int right){  //快排挖坑法
        int key = array[left];
        int i = left;
        while (left < right){
            while (left < right && array[right] >= key){
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= key){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }
    public static int partition1(int[] array,int left,int right){  //前后指针法
        int prev = left;
        int cur = left+1;
        while (cur <= right){
            if (array[cur] < array[left] && array[cur] != array[++prev]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }
    private static void swap(int[] array,int a,int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }


    public static void main(String[] args) {
        int[] array = {13,25,7,13,51,66};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }


}